package ljl.alg.jianzhioffer.round2;

public class _66_product_arr {
    /**
     * 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，
     * 其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积,
     * 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法
     *
     * 看着有点吓人，其实非常的简单
     * 但可能也没那么简单
     *
     * b0 -    a1 a2 a3..
     * b1 - a0    a2 a3 ..
     * b2 - a0 a1
     * ..
     * b3 - a0 a1 a2    ..
     *
     * 要是看答案一下就出来了，就成背题了
     * 还是先自己想想吧
     *
     * 蒙出来了；
     * 给我的感觉：9 9乘法表，毫无难度
     *
     * */
    public int[] constructArr(int[] a) {
        if (a.length == 0) return new int[0];
        int len = a.length;
        int[] b = new int[len];
        int[] c = new int[len];
        int[] d = new int[len];
        c[0] = 1; d[len - 1] = 1;
        for (int i = 1; i < len; i++) {
            c[i] = c[i - 1] * a[i - 1];
        }
        for (int i = len - 2; i >= 0; i--) {
            d[i] = d[i + 1] * a[i + 1];
        }
        for (int i = 0; i < len; i++) {
            b[i] = c[i] * d[i];
        }
        return b;
    }
}
